import java.util.Comparator;

/**
 * This is an implementation of a heap that is backed by an array.
 * 
 * This implementation will accept a comparator object that can be used to
 * define an ordering of the items contained in this heap, other than the
 * objects' default compareTo method (if they are comparable). This is useful if
 * you wanted to sort strings by their length rather than their lexicographic
 * ordering. That's just one example.
 * 
 * Null should be treated as positive infinity if no comparator is provided. If
 * a comparator is provided, you should let it handle nulls, which means it
 * could possibly throw a NullPointerException, which in this case would be
 * fine.
 * 
 * If a comparator is provided that should always be what you use to compare
 * objects. If no comparator is provided you may assume the objects are
 * Comparable and cast them to type Comparable<T> for comparisons. If they
 * happen to not be Comparable you do not need to handle anything, and you can
 * just let your cast throw a ClassCastException.
 * 
 * This is a minimum heap, so the smallest item should always be at the root.
 * 
 * @param <T>
 *            The type of objects in this heap
 */
public class BinaryHeap<T> implements Heap<T> {

	/**
	 * The comparator that should be used to order the elements in this heap
	 */
	private Comparator<T> comp;

	/**
	 * The backing array of this heap
	 */
	private T[] data;

	/**
	 * The number of elements that have been added to this heap, this is NOT the
	 * same as data.length
	 */
	private int size;

	/**
	 * Default constructor, this should initialize data to a default size (11 is
	 * normally a good choice)
	 * 
	 * This assumes that the generic objects are Comparable, you will need to
	 * cast them when comparing since there are no bounds on the generic
	 * parameter
	 */
	@SuppressWarnings("unchecked")
	public BinaryHeap() {
		comp = null;
		data = (T[]) new Object[11];}
	
	/**
	 * Constructor that accepts a comparator to use with this heap. Also
	 * initializes data to a default size.
	 * 
	 * When a comparator is provided it should be preferred over the objects'
	 * compareTo method
	 * 
	 * If the comparator given is null you should attempt to cast the objects to
	 * Comparable as if a comparator were not given
	 * 
	 * @param comp
	 */
	@SuppressWarnings("unchecked")
	public BinaryHeap(Comparator<T> comp) {
		this.comp = comp;
		data = (T[]) new Object[11]; }

	@SuppressWarnings("unchecked")
	@Override
	public void add(T item) {
		if (size>=data.length-1){ 
			T[] table = (T[]) new Object[data.length*2];  // new table
			for (int i=1;i<data.length;i++)
				table[i] = data[i];
			data = table;}			
		data[size+1] = item;
		up(size+1); // shift
		size++;}

	@Override
	public boolean isEmpty() {
		if (size==0) return true;
		return false;}

	@Override
	public T peek() {
		return data[1];	}

	@Override
	public T remove() {
		T removed = data[1];
		if (size!=0) {
			data[1] = data[size];
			data[size] = null;
			down(1);}
		size--;
		return removed;}

	@Override
	public int size() {
		return size;}

	private void swap(int a, int b){
		T temp = data[a];
		data[a] = data[b];
		data[b] = temp;
		down(b);}
	
	@SuppressWarnings("unchecked")
	private void down(int ndx) {
		int ndx2 = ndx*2+1;
		if (ndx*2<data.length && ndx2<data.length && ndx<size) {
			if (comp == null) {
				if(data[ndx*2]==null){
					if((data[ndx]==null && data[ndx*2]!=null)) swap(ndx,ndx*2);
					else if(data[ndx*2]!=null && ((Comparable<T>) data[ndx]).compareTo(data[ndx*2])>0) swap(ndx,ndx*2);}
				else{
					if(data[ndx2]!=null){
						if(((Comparable<T>) data[ndx2]).compareTo(data[ndx*2])>=0){ 
							if(data[ndx]==null || ((Comparable<T>) data[ndx]).compareTo(data[ndx*2])>0){
								swap(ndx,ndx*2);}}
						else{
							if(data[ndx]==null || ((Comparable<T>) data[ndx]).compareTo(data[ndx2])>0)
								swap(ndx,ndx2);}}
					else if(data[ndx*2]==null){
						if(data[ndx]==null || ((Comparable<T>) data[ndx]).compareTo(data[ndx2])>0)
							swap(ndx,ndx2);}}}
			else{
				if(data[ndx*2]==null){
					if(data[ndx]==null || comp.compare(data[ndx],data[ndx*2])<0)
						swap(ndx,ndx*2);}
				else{
					if(data[ndx2]!=null){
						if(comp.compare(data[ndx*2],data[ndx2])<0){
							if(data[ndx]==null || comp.compare(data[ndx],data[ndx*2])<0)
								swap(ndx,ndx*2);}
						else{
							if(data[ndx]==null || comp.compare(data[ndx],data[ndx2])<0)
								swap(ndx,ndx2);}}
					else if(data[ndx*2]==null){
						if(data[ndx]==null || comp.compare(data[ndx],data[ndx2])<0)
							swap(ndx,ndx2);}}}
		}
	}

	@SuppressWarnings("unchecked")
	private void up(int ndx) {
		int ndx2 = ndx/2;	//set ndx2
		if (!(data[ndx]==null||((ndx2)==0))) {
			if (comp == null) {
				if(data[ndx2]==null){
					data[ndx2] = data[ndx];
					data[ndx] = null;
					up(ndx2);}
				if (data[ndx]!=null && data[ndx2]!=null && ((Comparable<T>) data[ndx2]).compareTo(data[ndx])>0) {
					T temp = data[ndx2];
					data[ndx2] = data[ndx];
					data[ndx] = temp;
					up(ndx2);}}
			else {
				if(data[ndx2]==null){
					data[ndx2] = data[ndx];
					data[ndx] = null;
					up(ndx2);}
				if (data[ndx]!=null && data[ndx2]!=null && comp.compare(data[ndx],data[ndx2])<0) {
					T temp = data[ndx2];
					data[ndx2] = data[ndx];
					data[ndx] = temp;
					up(ndx2);}
			}
		}
	}
	
}